1. Field of the Invention
The present invention relates to systems for routing data through one or more networks. More specifically, the invention provides a system for minimizing unnecessary routing calculations in a network environment and thereby improves the utilization of computational resources.
2. Background
Data communication networks may include various nodes, routers, switches, hubs, and other network devices coupled to and communicating with one another. Data is communicated between network devices by utilizing links between the devices. A particular data packet (or data cell) may be handled by multiple network devices and cross multiple links as it travels between a source and a destination. Additionally, multiple networks may be coupled to one another by common network devices or common links.
Various protocols can be used to communicate routing information through a network. One type of protocol is referred to as a link state protocol, in which each node in the network knows the network topology such that the node can calculate routes through the network using the known topology. The link state information is distributed to network nodes using a series of Link State Advertisements (LSAs) originated by routers and other nodes in the network. For example, a router may advertise LSAs into the network area in which the router resides. These advertised LSAs may indicate that the router has connections to one or more nodes. These LSAs are received by other routers and nodes in the network. Thus, the other routers and nodes learn of the connections described in the advertised LSAs. All routers in the network may generate and advertise similar LSAs.
Since each router "learns" the network topology by receiving various LSAs, each router is capable of independently calculating routes through the network.
An example of a link state routing protocol is the Open Shortest Path First (OSPF) routing protocol. Each router running the OSPF protocol maintains an identical database describing the network topology. Using this topology database, each router is able to generate a routing table by constructing a shortest-path tree with the router at the root of the tree. OSPF is a dynamic routing protocol; i.e., OSPF detects changes in network topology and recalculates paths based on the new topology. Typically, all routers in an autonomous network run the OSPF protocol simultaneously.
OSPF allows multiple networks and routers to be grouped together. These groupings are commonly referred to as areas. The specific topology of a particular area is not broadcast to other areas. Instead, a summary of the area topology is transmitted to other areas, thereby reducing the amount of link state information that must be transmitted through the network. Since a router may be connected to more than one area, each router that borders multiple areas maintains a separate topology database for each area. A separate copy of OSPF's basic routing algorithm is executed in each area. Additionally, routing within a particular area is determined only by the topology of the particular area. Each area may use a different authentication scheme, such that some areas use stricter authentication schemes than other areas.
Mutlticast Open Shortest Path First (MOSPF) is a multicasting extension to OSPF. Multicasting is the distribution of data from a source to multiple destinations. The multiple destinations may be members of a multicast group such that each member of a multicast group receives data addressed to the group. By adding a new type of LSA, the group membership LSA, MOSPF is able to determine the location of all multicast group members in the network.
In standard MOSPF, a multicast tree for a source-group flow is calculated (or constructed) in each area to reach all possible routers and networks (and hence all group members) in that area. During the construction of the multicast tree, group member information is checked when a vertex (a router or a network) is moved from the candidate list to the Shortest Path First (SPF) tree. The SPF tree contains multiple vertices and various information related to each vertex in the tree. The information related to each vertex may include the type of vertex (e.g., a router or a network), the vertex ID, and information regarding the link(s) associated with the vertex. Each vertex in the SPF tree includes a pointer to the parent of the vertex.
If a vertex is downstream from the calculating router and has associated group members, then the calculating router's interface that leads to the vertex becomes a downstream interface for the source-group flow. In this situation, an entire tree is constructed even if there is no group member in the area, thereby inefficiently utilizing computational resources.
When new router LSAs or network LSAs are received or originated, all multicast forwarding entries are deleted and the new forwarding entries are recalculated on demand (i.e., new multicast trees are constructed on demand in all areas). When a new group membership LSA is received or originated, all the multicast forwarding entries related to the group are also deleted and then recalculated on demand in all the areas. This complete reconstruction of multicast trees inefficiently utilizes computational resources in a multi-area situation because it is likely that only a small portion of the forwarding entries need to be reconstructed in some areas.
It is therefore desirable to provide a system that minimizes unnecessary calculations of multicast trees and thereby improves the efficient utilization of computational resources.